Integer Divides Sum of Coprime Numbers Less Than It

Theorem

For any integer \(n > 2\) we have that

\[ n \mid \sum_{\substack{1 \leq k \leq n - 1 \\ \gcd(n, k) = 1}} k.\]

Proof

Consider the sum on the right reduced modulo \(n\), noting that of course \(\gcd(n, k) = \gcd(n, n - k)\). This means that for each \(k\) which appears on the right hand side, so does \(n - k\) given also that

\[ 1 \leq k \leq n - 1 \implies 1 \leq n - k \leq n - 1.\]

When adding these pairs, we have \(k + n - k = n \equiv 0 \pmod n\). As such, we can pair all elements in the sum such that each pair adds to zero.

The only way in which this may fail is if \(k = n - k\), however this implies \(n = 2k\) and since \(\gcd(k, n) = 1\), this means that \(k = 1\) and \(n = 2\), a case which we disregarded in the assumption of the theorem, and for which the result does not hold.